Rolling stock rostering is one of the basic planning problems in rail transport. It deals with the construction of rotations for individual units of rolling stock and, simultaneously, the composition of trains from these units. We focus on (long distance) passenger transport. Here, units of different types are arranged to form trains in particular sequences and orientations, and in a "regular" way.

Our approach to rolling stock rostering is based on a novel directed hypergraph model of the problem, which serves as a universal tool to handle several types of rules.

Poster (PDF)

We distinguish four types of regularity:

  • Operational regularity: Train turns should be regular, i.e., if train 4711 ends in Frankfurt and continues as 4712 on Monday, this should also be the case on Tuesday, Wednesday, etc., if possible.
  • Sequence regularity: Train compositions should be regular, i.e., train 4711 consists of the same types of rolling stock, in the same sequence and orientation, every day of the week. This type of regularity is well known from car position indicators.
  • Representational regularity: In the visualization of vehicle rotation plans similar weekdays of operation should be grouped into one rotation day.
  • Rotation regularity: Rotations of units of rolling stock should not be subdivided into many parts. This aims at a uniform wear and tear.

Regularity makes the operation of a railroad easier and more transparent by creating a routine way of handling all matters involved.

Our approach to rolling stock rostering is based on a novel hypergraph model of the problem, which serves as a universal tool to handle all types of train composition rules including sequencing, orientation, operational, and sequence regularity. In this model, vehicle rotations can be expressed in terms of hyperassignments.

Hyperassignments are generalizations of assignments. Our research dealt with hyperassignments in general and hyperassignments on what we call partitioned hypergraphs. The latter have a special hyperarc structure that applies to vehicle rotation planning models. We proved the hyperassignment problem to be NP-hard, even for partitioned hypergraphs with hyperarcs of maximum size two. Further, the canonical integer linear programming formulation results in large integrality gaps and arbitrarily high basis matrix determinants.

Calculations with practical data showed that clique inequalities highly reduce the LP-IP gap when added to the canonical integer program and therefore are of great importance. We proposed an extended formulation of the hypergraph assignment problem, which provably implies all clique inequalities and can be solved by column generation. Building on these results, we started a polyhedral investigation that has so far identified a number of interesting classes of cut inequalities.

Hyperassignment polyhedra have a complex structure even for small problems. We have classified the facets for the partitioned case with hyperarc size at most two and at most 6 vertices. We plan to expand and generalize our insights from this study to hyperassignment problem polyhedra for problems with more vertices and greater maximum hyperarc sizes. Developing graph decomposition, shrinking, and lifting procedures, we want to make these results usable to solve large-scale problems. Our experiments also indicate that hyperassignment problems can be approximated well by using a small number of important facets. We are therefore trying to identify special structures that give rise to approximation results, and that would also be useful in practical implementations.

Further, it would be helpful to find classes of directed hypergraphs for which the hyperassignment problem can be solved in polynomial time. This could lead to approximation algorithms using modification of the objective function. Moreover, we want to broaden our research to hyperassignments in multi-commodity settings, which are relevant in rolling stock rostering models.

Publications

2021
Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization Informs Journal on Applied Analytics, 51(1), pp. 42-62, 2021 Ralf Borndörfer, Thomas Eßer, Patrick Frankenberger, Andreas Huck, Christoph Jobmann, Boris Krostitz, Karsten Kuchenbecker, Kai Moorhagen, Philipp Nagl, Michael Peterson, Markus Reuther, Thilo Schang, Michael Schoch, Hanno Schülldorf, Peter Schütz, Tobias Therolf, Kerstin Waas, Steffen Weider BibTeX
DOI
Rolling Stock Roster Planning for Railways
2015
The hypergraph assignment problem Discrete Optimization, Vol.15, pp. 15-25, 2015 (preprint available as ZIB-Report 12-14) Ralf Borndörfer, Olga Heismann PDF (ZIB-Report)
PDF (ZIB-Report)
BibTeX
DOI
Rolling Stock Roster Planning for Railways
2014
A Generalization of Odd Set Inequalities for the Set Packing Problem Operations Research Proceedings 2013, pp. 193-199, 2014 (preprint available as ZIB-Report 14-28) Olga Heismann, Ralf Borndörfer PDF (ZIB-Report)
BibTeX
DOI
Rolling Stock Roster Planning for Railways
An Approximation Result for Matchings in Partitioned Hypergraphs ZIB-Report 14-30 (Appeared in: Operations Research Proceedings 2014 (2016) pp. 31-36.) Isabel Beckenbach, Ralf Borndörfer PDF
BibTeX
URN
DOI
Rolling Stock Roster Planning for Railways
The Hypergraph Assignment Problem Doctoral thesis, Technische Universität Berlin, Ralf Borndörfer, Martin Grötschel (Advisors), 2014 Olga Heismann BibTeX
Rolling Stock Roster Planning for Railways
2013
HUHFA: A Framework for Facet Classification ZIB-Report 13-45 Olga Heismann, Achim Hildenbrandt, Francesco Silvestri, Gerhard Reinelt, Ralf Borndörfer PDF
BibTeX
URN
Rolling Stock Roster Planning for Railways
Special cases of the hypergraph assignment problem Master's thesis, Technische Universität Berlin, Martin Grötschel, Ralf Borndörfer (Advisors), 2013 Isabel Beckenbach PDF
BibTeX
URN
Rolling Stock Roster Planning for Railways
The Random Hypergraph Assignment Problem Proceedings of the 16th International Multiconference INFORMATION SOCIETY - IS 2013, pp. 599-602, 2013 Olga Heismann, Ralf Borndörfer PDF
BibTeX
Rolling Stock Roster Planning for Railways
2012
Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning Operations Research Proceedings 2011, pp. 59-64, 2012 (preprint available as ZIB-Report 11-46) Olga Heismann, Ralf Borndörfer PDF (ZIB-Report)
BibTeX
Rolling Stock Roster Planning for Railways
Railway Track Allocation -- Simulation, Aggregation, and Optimization Proc. 1st International Workshop on High-speed and Intercity Railways (IWHIR 2011), 2(148), pp. 53-70, 2012 (preprint available as ZIB-Report 11-35) Ralf Borndörfer, Thomas Schlechte, Elmar Swarat PDF (ZIB-Report)
BibTeX
DOI
Rolling Stock Roster Planning for Railways
Vehicle Rotation Planning for Intercity Railways Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12), 2012 (preprint available as ZIB-Report 12-11) Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Steffen Weider PDF (ZIB-Report)
BibTeX
Rolling Stock Roster Planning for Railways
2011
A Hypergraph Model for Railway Vehicle Rotation Planning 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, OpenAccess Series in Informatics (OASIcs)(20), pp. 146-155, 2011 (preprint available as ZIB-Report 11-36) Ralf Borndörfer, Markus Reuther, Thomas Schlechte, Steffen Weider PDF (ZIB-Report)
BibTeX
DOI
Rolling Stock Roster Planning for Railways
Micro–macro transformation of railway networks Journal of Rail Transport Planning & Management, 1(1), pp. 38-48, 2011 (preprint available as ZIB-Report 10-23) Thomas Schlechte, Ralf Borndörfer, Berkan Erol, Thomas Graffagnino, Elmar Swarat PDF (ZIB-Report)
BibTeX
DOI
Rolling Stock Roster Planning for Railways
2010
Railway Track Allocation by Rapid Branching Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Thomas Erlebach, Marco Lübbecke (Eds.), pp. 13-23, Vol.14, OpenAccess Series in Informatics (OASIcs), 2010 (preprint available as ZIB-Report 10-22) Ralf Borndörfer, Thomas Schlechte, Steffen Weider PDF (ZIB-Report)
BibTeX
DOI
Rolling Stock Roster Planning for Railways